package srcInterviewPrep;

public final class SortedLinkedListMerger
{
    public static LinkedListNode MergeSortedLinkedLists(
        LinkedListNode h1,
        LinkedListNode h2)
    {
        // Argument validations

        LinkedListNode h;
        LinkedListNode t;

        if (h1.data < h2.data)
        {
            h = h1;
            t = h1;
            h1 = h1.next;
        }
        else
        {
            h = h2;
            t = h2;
            h2 = h2.next;
        }

        while (
            h1 != null
            && h2 != null)
        {
            if (h1.data < h2.data)
            {
                t.next = h1;
                h1 = h1.next;
            }
            else
            {
                t.next = h2;
                h2 = h2.next;
            }

            t = t.next;
        }

        if (h1 == null)
        {
            t.next = h2;
        }
        else
        {
            t.next = h1;
        }

        return h;
    }
}
